This invention arises out of the desire to improve packet switching. As may be recalled, a "packet" is defined by the CCITT (the Consultative Committee on International Telegraph and Telephone of the International Telecommunications Union) as a group of binary digits including formatted data and call control signals which is switched as a composite whole. Relatedly, "packet switching" is taken to mean the transmission of data by means of addressed packets whereby a channel is occupied only during packet transmission. As pointed out both by Martin, "Telecommunications and the Computer", second edition, pages 457-481; 1976, and Davies, et al, "Communication Networks for Computers", Chapter 13; 1973, packet switching is intended primarily for real time machine-to-machine traffic. In this regard, a packet switching network of nodes and links is expected to deliver its packet in a fraction of a second, whereas a message switching system intended primarily for non-real time people-to-people traffic typically delivers its message in a fraction of an hour.
Generally, packet switching systems using demand access and broadcast transmission over a cable medium employ a carrier-sense function in which each port, prior to transmission, ascertains whether the communication path is free, i.e. Metcalfe et al, U.S. Pat. No. 4,063,220. Upon idle path detection, a port then transmits onto the medium. During transmission, if collision is detected, then the sending port backs off and retries after a random interval. While a port is transmitting, collision is detected by an analog comparison of the send and receive wave forms by each originating port. The non-correspondence of the signals creates an ambiguity as to the cause of the garbled transmission. That is, the garbled received signal may be due to sources other than a colliding port, such as attenuation in a constrained channel, noise, reflections and/or standing waves. This ambiguity further reduces the communication efficiency of the common path/medium.
Metcalfe, et al, U.S. Pat. No. 4,063,220, "Multipoint Data Communication System with Collision Detection", issuing Dec. 13, 1977, typifies this system. Metcalfe does send a jamming pattern to all ports indicating the original message was aborted. In contrast, Fitch et al, U.S. Pat. No. 3,914,743, "Data System Multi-Branch Junction Circuit, etc.", issuing Oct. 21, 1975, teaches the use of a junction circuit operative as a root node in an inverted tree network where up-linked data is multiplexed, with neither locking nor collision management, and where down-linked data is broadcast. Relatedly, the inverted tree geometry makes each node a concentrator. Each port terminates in a node and avoids contention in a tree geometry.
In demand access and broadcast transmission systems, the utility of semaphore techniques for resolving contention among asynchronous ports is believed limited. Broadly, semaphore techniques for a single CPU ensure synchronism among parallel tasks accessing serially reusable (temporally distributed) resources. However, the networking inherent in communication systems requires synchronism of spatially distributed resources as well as resources available over time. By this it is meant that the short distances within a CPU render point-to-point signal transmission near instantaneous whereas in a spaced apart network, propagation considerations in addition to timing must be taken into account.
Among other networks reporting broadband transmission are those in which a bus is time shared among ports directly coupling the bus. Two spatially separated ports signify the existence of a finite propagation delay from one to the other. This results in a difficulty of ensuring queued access to the bust except by way of a serialized or external status indication to each port. Protocols involving waiting reduce the transmission rate in a high-speed packet transmission system, if waiting is required each time prior to transmission. This is exemplified in the hydraulic analogy of multiple ports accessing a shared pipe in which it would be necessary to drain the pipe prior to the insertion of a new message (water injection from one port destined to other ports). Such a bus/port logic arrangement is described in copending patent application U.S. Ser. No. 053,493, filed on June 29, 1979, entitled Port Logic for a Communication Bus System, by Eswaran, et al.